package com.gitee.alg.sort

/**
 * Project Name: alg
 * Des:选择排序
 * 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
 * 算法步骤
 *    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 *    再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * Package:com.gitee.alg.sort
 * @author Arlo Sun
 * @date 2021/4/26 - 15:52
 */
class SelectionSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {

    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        for (i in 0 until array.size - 1) {
            var index = i
            //初始以数组第一个元素作为起始最小值
            var smallest = array[i]

            //i+1起始，因为前面的已经有序（只有一个元素的数组是有序的）
            for (j in i + 1 until array.size) {
                // if smallest > array[j] -> smallest = array[j]
                if (compare(smallest, array[j])) {
                    index = j
                    smallest = array[j]
                }
            }

            //前面遍历完后一定能找到最小的元素放在当前有序队列末端
            array.swap(i, index)
        }

        return array
    }
}